package com.rw.tool.util.expression.expression;

import com.rw.tool.util.expression.element.*;
import com.rw.tool.util.expression.exception.CheckInfixExpressionException;
import com.rw.tool.util.expression.expression.parser.InfixExpressionParser;
import com.rw.tool.util.expression.expression.tree.ElementNode;
import com.rw.tool.util.expression.state.InfixExpressionState;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀表达式
 */
public class InfixExpression extends Expression {
    public InfixExpression(List<ExpressionElement> elements) {
        super(elements);
        assertExpression(elements);
    }

    protected InfixExpression() {
    }

    @Override
    public ElementNode getRootNode() {
        // 先转为后缀表达式
        List<ExpressionElement> postfix = infixToPostfix(getElements());
        return getRootNode(postfix, false);
    }

    /**
     * 验证表达式是否合法
     */
    public static boolean checkExpression(List<ExpressionElement> elements) {
        try {
            assertExpression(elements);
        } catch (CheckInfixExpressionException exception) {
            return false;
        }
        return true;
    }

    /**
     * 验证表达式是否合法，若不合法，则抛出异常
     */
    public static void assertExpression(List<ExpressionElement> elements) {
        // 初始化状态
        InfixExpressionState state = InfixExpressionState.START;

        int index = 0;
        for (ExpressionElement element : elements) {
            if (!state.canBeFollowed(element)) {
                throw new CheckInfixExpressionException(state, elements, index);
            }
            state = InfixExpressionState.of(element);
            index++;
        }

        if (state != InfixExpressionState.AFTER_RIGHT_PARENTHESES && state != InfixExpressionState.AFTER_NUMBER) {
            throw new CheckInfixExpressionException(state, elements, index);
        }
    }

    /**
     * 解析字符串，使其变为合法的表达式列表
     * 如果字符串不符合中缀表达式结构，则会抛出异常
     * scale代表精确到小数点后几位
     */
    public static InfixExpression parse(String expression, int scale) {
        InfixExpressionParser parser = new InfixExpressionParser();
        return parser.parse(expression, scale);
    }

    /**
     * 解析字符串，使其变为合法的表达式列表
     * 如果字符串不符合中缀表达式结构，则会抛出异常
     */
    public static InfixExpression parse(String expression) {
        return parse(expression, -1);
    }

    /**
     * 中缀表达式转前缀或后缀表达式
     */
    private static List<ExpressionElement> infixToPostfix(List<ExpressionElement> elements) {
        // 声明数字栈和符号栈
        Stack<Sign> signStack = new Stack<>();

        List<ExpressionElement> result = new LinkedList<>();
        for (ExpressionElement element : elements) {
            // 如果元素为数字，则将数字输出
            if (element instanceof NumberElement) {
                // 输出这个数字
                result.add(element);
                continue;
            }

            // 如果元素为左括号，则将括号入栈。
            if (element instanceof LeftParentheses) {
                signStack.push((Parentheses) element);
                continue;
            }

            // 如果元素为右括号，则一直出栈到左括号。
            if (element instanceof RightParentheses) {
                // 获取被弹出的元素，并加入表达式中
                result.addAll(popUntilParentheses(signStack));
                continue;
            }

            // 如果元素为普通计算符号
            Calculation calculation = (Calculation) element;
            // 获取被弹出的元素，并加入表达式中
            result.addAll(popUntilTargetPriority(signStack, calculation.getPriority()));

            // 将当前的符号放入栈
            signStack.push(calculation);
        }

        // 把剩余的元素放入表达式
        while (!signStack.isEmpty()) {
            result.add(signStack.pop());
        }

        return result;
    }

    /**
     * 把一个栈按顺序弹出，直到弹出括号
     * 并且返回被弹出的表达式元素
     */
    private static List<ExpressionElement> popUntilParentheses(Stack<Sign> signStack) {
        List<ExpressionElement> postfix = new LinkedList<>();
        while (!(signStack.peek() instanceof Parentheses)) {
            postfix.add(signStack.pop());
        }
        // 把剩下的这个左括号也给出栈了
        signStack.pop();

        return postfix;
    }

    /**
     * 把一个栈按顺序弹出，直到弹出到优先级小于目标值的符号
     */
    private static List<ExpressionElement> popUntilTargetPriority(Stack<Sign> signStack, int targetPriority) {
        List<ExpressionElement> postfix = new LinkedList<>();
        // 如果优先度大于等于目标优先度，则出栈
        while (!signStack.isEmpty() && priorityBelow(signStack.peek(), targetPriority)) {
            postfix.add(signStack.pop());
        }
        return postfix;
    }

    /**
     * 优先度大于等于
     */
    private static boolean priorityBelow(Sign sign, int targetPriority) {
        if (!(sign instanceof Calculation)) {
            return false;
        }
        Calculation calculation = (Calculation) sign;
        return calculation.getPriority() >= targetPriority;
    }
}
